#include <iostream>
#include <algorithm>
#include <cassert>
#include <exception>
#include <stdexcept>

using namespace std;

int const CHUNK = 10;

template<typename T>
class Deque 
{
public:
	Deque();
	~Deque(){ delete [] subDeque; }
	void push_front(T val);
	void push_back(T val);
	T& front(); // Throws if deque is empty
	T& back(); // Throws if deque is empty
	T& at(int pos); // Throws if pos is out of range (0 through d.size()-1)
	void pop_front(); // No-op on underflow
	void pop_back(); // No-op on underflow
	int size() const;
	T* begin(); // Returns a pointer to the first element
	T* end(); // Returns a pointer to one past the last element
	void print();
private:
	void copy();
	void grow();
	int length() const;
	T *subDeque;
	T* dequeFront;
	T* dequeBack;
	int Length;
	int count;
	T testDeque[100];
};

template <typename T> Deque<T>::Deque()
{
	subDeque = new T [CHUNK];
	Length = CHUNK;
	dequeFront = dequeBack = subDeque + (length()-1)/2;
	count = 0;
}
template <typename T> void Deque<T>::copy()
{
	for(int i = 0; i < Length; i ++)
	{
		testDeque[i] = subDeque[i];
	}
}
template <typename T> void Deque<T>::print()
{
	for(int i = 0; i < size(); i ++)
	{
		cout << dequeFront[i + 1] << " ";
	}
	cout << "\t" << *dequeFront << " " << *dequeBack << endl << endl;
}

template <typename T> void Deque<T>::grow()
{
	T *subDequeTmp = new T [size()];
	for (int i = 0; i <= size(); i ++)
	{
		subDequeTmp[i] = subDeque[i];
	}
	subDeque = new T [size() + CHUNK];
	T *copyTmp = subDeque;
	for (int i = 0; i <= size() + (CHUNK/2); i++)
	{
		if (i < CHUNK/2)
		{
			copyTmp++;
		}
		else if (i == CHUNK/2)
		{
			dequeFront = subDeque + CHUNK/2 - 1;
			copyTmp[i - CHUNK/2] = subDequeTmp[i - (CHUNK/2)];
		}
		else
		{
			copyTmp[i - CHUNK/2] = subDequeTmp[i - (CHUNK/2)];
		}
	}
	dequeBack = subDeque + size() - 1 + CHUNK/2 ; 
	Length = size() + CHUNK;
}

template <typename T> void Deque<T>::push_front(T val)
{
	int tmp = length();
	if (count >= length())
	{
		grow();
	}
	*dequeFront = val;
	dequeFront --;
	count++;
	copy();
}

template <typename T> void Deque<T>::push_back(T val)
{
	int tmp = length();
	if (count == length())
	{
		grow();
	}
	dequeBack ++;
	*dequeBack = val;
	count ++;
	copy();
}

// Throws if deque is empty
template <typename T> T& Deque<T>::front()
{
	if (dequeFront == dequeBack)
	{
		throw logic_error("The deque is empty");
	}
	return *(dequeFront + 1);
}

// Throws if deque is empty
template <typename T> T& Deque<T>::back() 
{
	if (dequeFront == dequeBack)
	{
		throw logic_error("The deque is empty");
	}
	T &tmp = *(dequeBack);
	return tmp;
}

// Throws if pos is out of range (0 through d.size()-1)
template <typename T> T& Deque<T>::at(int pos)
{
	if (pos > size()-1)
	{
		throw logic_error("Possition out of bounds");
	}
	T& tmp = *((dequeFront + 1) + pos);
	return tmp;
}

// No-op on underflow
template <typename T> void Deque<T>::pop_front() 
{
	if (dequeBack == dequeFront)
	{
		if (count != 0)
			count --;
		return;
	}
	dequeFront++;
	count--;
}

// No-op on underflow
template <typename T> void Deque<T>::pop_back()
{
	if (dequeBack == dequeFront)
	{
		if (count != 0)
			count --;
		return;
	}
	dequeBack--;
	count--;
}

template <typename T> int Deque<T>::size() const
{
	return count;
}

template <typename T> int Deque<T>::length() const
{
	return Length;
}

// Returns a pointer to the first element
template <typename T> T* Deque<T>::begin()
{
	return (dequeFront + 1);
}

// Returns a pointer to one past the last element
template <typename T> T* Deque<T>::end()
{
	return (dequeBack + 1);
}
